Tỉnh Nam Sumatra từ thế kỷ trước còn được gọi là Srivijaya vì từ thế kỷ thứ 7 cho đến thế kỷ thứ 12 khu vực này là trung tâm của vương quốc Srivijaya. Đây là vương quốc hàng hải lớn nhất và mạnh nhất trong quần đảo. Tiếng vang và ảnh hưởng của nó thậm chí đến đảo Madagascar tại châu Phi. Kể từ thế kỷ 13 cho đến thế kỷ 14, khu vực này nằm dưới sự cai trị của Majapahit. Tuy nhiên, khu vực này đã trở thành những vùng đất vô chính phủ và nạn cướp biển hoành hành, đặc biệt là từ Trung Quốc. Theo một số nghiên cứu, vương quốc Srivijaya được thành lập vào ngày 17 tháng 6, 683. Ngày này sau đó đã trở thành một ngày kỷ niệm hàng năm tại Palembang.

Tỉnh Nam Sumatra được chia ra 11 huyện và 4 thành phố: